package search;

/**
 * 二分查找
 * @author Tang Jiujia
 * @since 16:06 2020-04-13
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 4, 5, 5, 6, 9, 10, 15};
        System.out.println(binarySearchForFirstGreaterOrEqual(arr, 6));
    }

    /**
     * 二分查找
     *
     * @param arr 被查找的数组
     * @param value	要查找的值
     * @return int 对应值的数组下标，如果没有返回-1
     */
    private static int binarySearch(int[] arr, int value) {
        int len = arr.length;
        int h = len - 1;
        int l = 0;
        while (l <= h) {
            int mid = (l + h) / 2;
            int midValue = arr[mid];
            if (midValue == value) {
                return mid;
            } else if (midValue < value) {
                l = mid + 1;
            } else {
                h = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 使用二分查找找到第一个等于指定值的数组索引
     *
     * @param arr 被查找的数组
     * @param value 要查找的值
     * @return int 数组索引
     */
    private static int binarySearchForFirst(int[] arr, int value) {
        int len = arr.length;
        int h = len - 1;
        int l = 0;
        while (l <= h) {
            int mid = l + ((h - l) >> 1);
            int midValue = arr[mid];
            if (midValue > value) {
                h = mid - 1;
            } else if (midValue < value) {
                l = mid + 1;
            } else {
                if ((mid == 0) || (arr[mid - 1] != value)) {
                    return mid;
                } else {
                    h = mid - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 使用二分查找找到最后一个等于指定值的数组索引
     *
     * @param arr
     * @param value
     * @return int 数组索引
     */
    private static int binarySearchForLast(int[] arr, int value) {
        int len = arr.length;
        int h = len - 1;
        int l = 0;
        while (l <= h) {
            int mid = l + ((h - l) >> 1);
            int midValue = arr[mid];
            if (midValue > value) {
                h = mid - 1;
            } else if (midValue < value) {
                l = mid + 1;
            } else {
                if ((mid == (len - 1)) || (arr[mid + 1] != value)) {
                    return mid;
                } else {
                    l = mid + 1;
                }
            }
        }
        return -1;
    }

    /**
     * 使用二分查找在数组中找到第一个大于或等于给定值的数组索引
     *
     * @param arr
     * @param value
     * @return int 数组索引
     */
    private static int binarySearchForFirstGreaterOrEqual(int[] arr, int value) {
        int len = arr.length;
        int h = len - 1;
        int l = 0;
        while (l <= h) {
            int mid = l + ((h - l) >> 1);
            int midValue = arr[mid];
            if (midValue < value) {
                l = mid + 1;
            } else {
                if (mid == 0 || arr[mid - 1] < value) {
                    return mid;
                } else {
                    h = mid - 1;
                }
            }
        }
        return -1;
    }
}



